package com.gxc.slidingWindow;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */
public class MinWindow {

    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";

        Map<Character, Integer> ori = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            ori.put(t.charAt(i), ori.getOrDefault(t.charAt(i), 0) + 1);
        }

        int l = 0, r = 0;
        int min = Integer.MAX_VALUE;
        int start = -1;
        //当前的滑动窗口
        Map<Character, java.lang.Integer> cur = new HashMap<>();
        while (r < s.length()) {
            Character c = s.charAt(r);
            cur.put(c, cur.getOrDefault(c, 0) + 1);
            r++;
            while (check(ori, cur) && l<r) {
                if (r - l < min) {
                    start = l;
                    min = r - l;
                }
                Character q = s.charAt(l);
                cur.put(q, cur.getOrDefault(q, 0) -1);
                l++;
            }
        }
        return start == -1 ? "" :s.substring(start, start + min);
    }

    private boolean check(Map<Character, java.lang.Integer> ori, Map<Character, java.lang.Integer> cur) {
        for (Map.Entry<Character, Integer> characterIntegerEntry : ori.entrySet()) {
            if (characterIntegerEntry.getValue() > cur.getOrDefault(characterIntegerEntry.getKey(), 0)) {
                return false;
            }
        }
        return true;
    }

    public String minWindow2(String s, String t) {
        //目标的字符
        Map<Character, java.lang.Integer> ori = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0)+1);
        }

        //当前的滑动窗口
        Map<Character, java.lang.Integer> cur = new HashMap<>();

        int l = 0, r = 0;
        int min = java.lang.Integer.MAX_VALUE, minL = -1, minR = -1;
        int sl = s.length();
        while (r<sl) {
            char c = s.charAt(r);
            if (ori.containsKey(c)) {
                cur.put(c, cur.getOrDefault(c, 0)+1);
            }

            //窗口右侧不动，窗口左侧缩小
            while (satisfy(ori, cur) && l <= r) {
                if (r + 1 - l < min) {
                    min = r +1 -l;
                    minL = l;
                    minR = r+1;
                }
                //窗口左侧缩小，左侧字符移出窗口

                char ch = s.charAt(l);
                if (ori.containsKey(ch)) cur.put(ch, cur.get(ch) - 1);
                l++;
            }
            r++;
        }
        //涵盖 t 所有字符的字符串
        return minL == -1 ? "": s.substring(minL, minR);
    }

    private static boolean satisfy(Map<Character,java.lang.Integer> ori, Map<Character,java.lang.Integer> cur) {
        Iterator<Map.Entry<Character, Integer>> iterator = ori.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, java.lang.Integer> next = iterator.next();
            Character c = next.getKey();
            if (cur.getOrDefault(c, 0) < next.getValue()) return false;
        }
        return true;
    }

    /**
     * 优化版
     * @param s
     * @param t
     * @return
     */
    public String minWindow3(String s, String t) {
        int m = s.length(), n = t.length();
        int left = -1, right = 0, min = Integer.MAX_VALUE;
        int less = 0;

        int[] need = new int[128];
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            if (need[c] == 0) {
                less++;
            }
            need[c]++;
        }

        int l = 0,r = 0;
        while (r < m) {
            char c = s.charAt(r);
            need[c]--;
            if (need[c] == 0) {
                less--;
            }
            while (less == 0) {
                if (r - l < min) {
                    left = l;
                    right = r;
                    min = r - l;
                }
                char c1 = s.charAt(l);
                if (need[c1] == 0) {
                    less++;
                }
                need[c1]++;
                l++;
            }
            r++;
        }
        return left==-1?"":s.substring(left, right+1);
    }
}
